package problem_everyday;

import java.util.Arrays;
import java.util.Comparator;

public class D2025_07_08_P1571 {
    /*
    * events = {{start, end, value}}
    * 最多可以参加k个会议，使得总的value和最大化
    *
    * 解决方案：二维动态规划 + 二分查找
    * */
    // 寻找结束点在cur_start之前的第一个会议
    private int binarySearchFirstEvent(int[][] events, int cur_start, int left, int right){
        while(left<=right){
            int mid = left + (right - left) / 2;
            if(events[mid][1] >= cur_start){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int res = left - 1;
        return res;
    }

    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, new Comparator<int[]>(){
            public int compare(int[] a, int [] b){
                if(a[1] == b[1]){
                    return a[0] - b[0];
                } else return a[1] - b[1];
            }
        });
        // 在前i个会议中参加k个会议的最值
        /**
         不参加第i会议 dp[i-1][k]
         参加第i个会议 dp[m][k-1] + values[i] m是向前查找第一个不与会议i重合的会议
         dp[i][k] = max(dp[i-1][k])

         */

        int[][] dp = new int[events.length][k+1];
        int[] pre = new int[events.length];
        for(int i=1; i<events.length; i++){
            pre[i] = binarySearchFirstEvent(events, events[i][0], 0, i-1);
        }
        for(int i=1; i<=k; i++) dp[0][i] = events[0][2];
        for(int j = 1; j <= k; j++ ){
            for(int i=1; i<events.length; i++){
                int m = pre[i];
                if(m>=0)
                    dp[i][j] = Math.max(dp[i-1][j], dp[m][j-1] + events[i][2]);
                else
                    dp[i][j] = Math.max(dp[i-1][j], events[i][2]);
            }
        }
        return dp[events.length-1][k];
    }

    public static void main(String[] args) {
        D2025_07_08_P1571 p = new D2025_07_08_P1571();
        int[][] events = {{1,3,4},{2,4,1},{1,1,4},{3,5,1},{2,5,5}};
        int k = 3;
        System.out.println(p.maxValue(events, k));
    }
}
